In the mid-1980s, the Free Software Foundation launched a project to produce a complete set of software for the inexpensive and increasingly powerful computers then becoming available. In the decades since, thousands of amateur and professional software developers have contributed programs directly to the project, or have released “Open Source” software under terms that permit it to be used in a free (as in speech) system. Today, this software often equals or surpasses commercially-available software in quality and functionality, and viable ancillary businesses have developed to provide support and coordination services for computer owners who wish to take advantage of the wealth of available software.
Ironically, the enormous number of free and open-source software packages available causes problems for users when the independently-developed and maintained packages are modified or improved. For example, consider two applications, A1 and A2, which depend on functionality provided by a library L. If new features are added to the library and adopted by application A1, upgrading A1 and L may impair the operation of A2 (which has not yet been modified to use the new library). More generally, keeping track of the interdependencies of thousands of software packages that may be installed on a system is a daunting task.
Companies such as Red Hat Corporation of Raleigh, N.C., have built successful businesses by curating software package collections and developing system maintenance tools that make it easy to set up and operate a general-purpose computer using free and open-source software. Package upgrades are tracked and new versions are harmonized to provide a complete, coherent, functional system that carries the benefits of new features and fixed bugs, while avoiding the “bleeding edge” problems of inconsistent versions and support component incompatibilities. (Of course, Red Hat Corporation is more than a mere aggregator of others' software: Red Hat engineers also develop new applications and improve existing packages. Much of this work is released under permissive, open-source license terms, further enlarging the universe of free-software capability.)
A central problem in managing a software distribution comprising many interdependent components or “packages” is that of dependency resolution, where the implications of one change to a hardware-and-software configuration are analyzed recursively to determine what other changes to the configuration might also be required. Fortunately, this problem is reasonably well-understood. Apart from circular dependencies and a small set of similar pathological cases, dependency resolution can be carried out automatically, and the results used to control software installation, upgrade and removal operations. Unfortunately, the time required to perform a dependency resolution grows in proportion to the number of dependencies between components, and not just in proportion to the number of components. A method of caching the results of a dependency resolution can speed up operations when similar changes are to be made to multiple computers.